package graph.weighted.minimun_spanning_tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import graph.weighted.CandyWeightedEdge;
import graph.weighted.CandyWeightedGraph;
import graph.weighted.connectedComponent.CandyConnectedComponent;
import unionFound.CandyUnionFind;
import unionFound.CandyUnionFindImpl;
/**
 * 
 * @Title: CandyKruskal.java 
 * @Package graph.weighted.minimun_spanning_tree 
 * @Description: 求解最小生成树，kruskal算法
 * @author CandyWall   
 * @date 2021年1月20日 下午4:22:44 
 * @version V1.0
 */
public class CandyKruskal {
    private CandyWeightedGraph graph; 
    
    public CandyKruskal(CandyWeightedGraph graph) {
        this.graph = graph;
    }
    
    /**
     * 获取最小生成树中的所有边
     * @return
     */
    public ArrayList<CandyWeightedEdge> getMst() {
        ArrayList<CandyWeightedEdge> mst = new ArrayList<>();
        CandyConnectedComponent connectedComponent = new CandyConnectedComponent(graph);
        if(connectedComponent.getConnectedComponentCount() > 1) {
            return mst;
        }
        
        // Kruskal
        ArrayList<CandyWeightedEdge> edges = new ArrayList<>();
        for(int v = 0; v < graph.getVertex_num(); v++) {
            for(int w : graph.adjacentVertexes(v)) {
                // 避免重复添加边
                if(v < w) {
                    edges.add(new CandyWeightedEdge(v, w, graph.getWeight(v, w)));
                }
            }
        }
        
        Collections.sort(edges);
        // 创建一个并查集
        CandyUnionFind unionFind = new CandyUnionFindImpl(graph.getVertex_num());
        for(CandyWeightedEdge edge : edges) {
            int v = edge.getV();
            int w = edge.getW();
            if(!unionFind.isConnected(v, w)) {
                unionFind.unionElements(v, w);
                mst.add(edge);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph = new CandyWeightedGraph("testData/weightedGraph/graph.txt");
        CandyKruskal kruskal = new CandyKruskal(graph);
        System.out.println(kruskal.getMst());
    }
}
